扫描线整体二分(偏序整体二分)
P3242 [HNOI2015] 接水果
这是一道极好的神仙题,除了博弈论几乎没有任何其它题的思维有这题巧妙,其天才般的思想和知识点间美妙的融合让所有 OIer 叹为观止。确切地说,这是我此生见过的最巧妙的题,整体二分的实现也不由得让人对出题者产生由衷的钦佩。
注意到这居然是省选题。注意到我不知道风见幽香是谁。注意到这题居然是用盘子接水果而不是水果接盘子,盘子要被水果包含才能装住水果。
树上第 k 小,考虑整体二分,因为我们这篇的标题中整体二分排在最前面。假设我们的盘子是以下蓝色链条,x 和 y 是盘子的两个端点,z 是 x 在盘子上的儿子,能装住盘子的水果的两个端点为 u,v, 其中 depu<depvdep_u<dep_vdepu <depv (如果不是则将两个端点交换), u 和 v 的最近公共祖先是 u:
此时图中红色的部分即是 u 可能的范围,蓝色的部分即是 v 可能的范围。
如果 u 不是 v 的祖先,则:
可贡献的图就如上所示了。因此,询问 (x,y)(x,y)(x,y) 与 lcau,v=u\operatorname{lca}_{u,v}=ulcau,v =u 时 stu∈[1,stz)∣(edz,N],stv∈[sty,edy]st_u\in [1,st_z)|(ed_z,N],st_v\in [st_y,ed_y]stu ∈[1,stz )∣(edz ,N],stv ∈[sty ,edy ] 和当不满足 lcau,v=u\operatorname{lca}_{u,v}=ulcau,v =u 时 stu∈[stx,edx],stv∈[sty,edy]st_u\in
[st_x,ed_x],st_v\in [st_y,ed_y]stu ∈[stx ,edx ],stv ∈[sty ,edy ] 的果子 (u,v)(u,v)(u,v) 有关。我们注意到这个约束条件很像是矩形,把每个盘子看作一个矩形,它能装住的所有点都是能接住的果子。问题转化为求一个点所在的所有矩形中第 kkk 小的权值,判断时将 [0,mid][0,mid][0,mid] 的所有矩形加一然后单点查询。可以在每次整体二分中排序,然后用扫描线求出被标记的数有多少个并进行二分。由于扫描线自带一次撤销操作,因此不用在整体二分后再清空树状数组。
这个扫描线没有面积并和周长并里的那么麻烦,只需要在扫到入边时加权,扫到出边时减回去(是个人都会做)。
Code:
成功拿到此题最优解: